Organizations, such as companies, enterprises, and governments, execute processes with activities, tasks, business functions, and other operations that are collectively referred to as process steps.
In general, processes can be represented by process models that describe the interrelation between the steps.
More in particular, companies and enterprises execute business processes that are represented by business process models.
The models are stored and documented in a variety of forms and media, that range, for example, from traditional instructions on paper to modern computer-code in modeling languages.
User interfaces enable creation and modification of the computer-coded models by human users. There are many computer techniques available to present models graphically to the users as diagrams, flowcharts, or the like, to store models in repositories, and to let users create or modify the models.
The process steps may be executed (or performed) manually by humans, for example, by employees of the enterprise, or more and more automatically may be executed in whole or in part by machines that include computers.
With the rise of the so-called Service Oriented Architecture (SOA) of computer systems, process activities are getting more and more encapsulated in services, such as in web services. Therefore, the process models have become the backbones and fundamental control elements for complex software systems that arrange process execution by calling the services.
To stay with the example of the enterprises, these organizations need to quickly react to changing market situations, and consequently need to create new business processes or modify existing ones within short time. Similar requirements apply to organizations and processes in general.
However, the underlying models, especially the models implemented by computers, are usually created and modified with collaboration between persons that are process domain experts and persons that are computer domain experts.
Potential misunderstanding between the experts in both domains can lead to incorrect process execution. There is a trend to improve the user interfaces so that the computers can be operated by the process domain experts, who become process designers or modelers.
But still, human experts introduce errors, and before running a process (or, in other words, before deploying its model) it is important to validate the model, and thereby to verify the executability of the process (i.e. if the process can be executed without faults or not).
There are different validation aspects, such as to look at the control flow, or to check the semantic consistency of model and process, and so on.
Validation tools are usually implemented as computer programs that receive the model, for example, in the above-mentioned code in a modeling language. For example, the tools can visit each step of the model from the first to the last step, and check if the execution of the steps is possible. However, such validation runs may be expensive in terms of computer processing time. Very often, it would not be possible to analyze the model within so-called low-order polynomial time over the input size. From an economic point of view, the business processes would not become available for execution within a sufficiently short time. If model validation requires hours to execute, process designers might decide to skip validation, which would then put the execution of the process at risk.